use std::mem;
use std::ptr;

pub type QueueValue = *mut libc::c_void;

#[repr(C)]
pub struct QueueEntry {
    pub data: QueueValue,
    pub prev: *mut QueueEntry,
    pub next: *mut QueueEntry,
}

#[repr(C)]
pub struct Queue {
    pub head: *mut QueueEntry,
    pub tail: *mut QueueEntry,
}

impl Queue {
    pub fn new() -> *mut Queue {
        let queue = unsafe { libc::malloc(mem::size_of::<Queue>()) as *mut Queue };
        if queue.is_null() {
            return ptr::null_mut();
        }
        unsafe {
            (*queue).head = ptr::null_mut();
            (*queue).tail = ptr::null_mut();
        }
        queue
    }

    pub fn free(queue: *mut Queue) {
        while !Queue::is_empty(queue) {
            Queue::pop_head(queue);
        }
        unsafe {
            libc::free(queue as *mut libc::c_void);
        }
    }

    pub fn push_head(queue: *mut Queue, data: QueueValue) -> bool {
        let new_entry = unsafe { libc::malloc(mem::size_of::<QueueEntry>()) as *mut QueueEntry };
        if new_entry.is_null() {
            return false;
        }
        unsafe {
            (*new_entry).data = data;
            (*new_entry).prev = ptr::null_mut();
            unsafe {
                (*new_entry).next = (*queue).head;
            }
            if (*queue).head.is_null() {
                (*queue).head = new_entry;
                (*queue).tail = new_entry;
            } else {
                (*(*queue).head).prev = new_entry;
                (*queue).head = new_entry;
            }
        }
        true
    }

    pub fn pop_head(queue: *mut Queue) -> QueueValue {
        if Queue::is_empty(queue) {
            return ptr::null_mut();
        }
        unsafe {
            let entry = (*queue).head;
            (*queue).head = (*entry).next;
            let result = (*entry).data;
            if (*queue).head.is_null() {
                (*queue).tail = ptr::null_mut();
            } else {
                (*(*queue).head).prev = ptr::null_mut();
            }
            libc::free(entry as *mut libc::c_void);
            result
        }
    }

    pub fn peek_head(queue: *mut Queue) -> QueueValue {
        if Queue::is_empty(queue) {
            ptr::null_mut()
        } else {
            unsafe { (*(*queue).head).data }
        }
    }

    pub fn push_tail(queue: *mut Queue, data: QueueValue) -> bool {
        let new_entry = unsafe { libc::malloc(mem::size_of::<QueueEntry>()) as *mut QueueEntry };
        if new_entry.is_null() {
            return false;
        }
        unsafe {
            (*new_entry).data = data;
            (*new_entry).prev = (*queue).tail;
            unsafe {
                (*new_entry).next = ptr::null_mut();
            }
        }
        if unsafe { (*queue).tail.is_null() } {
            unsafe {
                (*queue).head = new_entry;
                (*queue).tail = new_entry;
            }
        } else {
            unsafe {
                (*(*queue).tail).next = new_entry;
                (*queue).tail = new_entry;
            }
        }
        true
    }

    pub fn pop_tail(queue: *mut Queue) -> QueueValue {
        if Queue::is_empty(queue) {
            ptr::null_mut()
        } else {
            unsafe {
                let entry = (*queue).tail;
                (*queue).tail = (*entry).prev;
                let result = (*entry).data;
                if (*queue).tail.is_null() {
                    (*queue).head = ptr::null_mut();
                } else {
                    (*(*queue).tail).next = ptr::null_mut();
                }
                libc::free(entry as *mut libc::c_void);
                result
            }
        }
    }

    pub fn peek_tail(queue: *mut Queue) -> QueueValue {
        if Queue::is_empty(queue) {
            ptr::null_mut()
        } else {
            unsafe { (*(*queue).tail).data }
        }
    }

    pub fn is_empty(queue: *mut Queue) -> bool {
        unsafe { (*queue).head.is_null() }
    }
}